package class10;

import java.util.*;

/**
 * https://leetcode.cn/problems/maximum-frequency-stack/
 * 最大频率栈
 * 1.栈内：[3, 5, 3, 5, 2]， 3有2次 5有2次 2有1次
 * 2.pop最大频率时，移除栈顶的5，
 * 3.栈内：[3, 5, 3, 2]， 3有2次，5有1次，2有1次
 * <p>
 * 解题思路：
 * 1.
 */
public class Code14_FreqStack {
    public static void main(String[] args) {
        FreqStack freqStack = new FreqStack();
        freqStack.push(3);
        freqStack.push(5);
        freqStack.push(3);
        freqStack.push(5);
        freqStack.push(2);
        System.out.println();
    }

    private static class FreqStack {
        Map<Integer, List<Integer>> cntValueMap; // 存次数对应的值
        Map<Integer, Integer> keyCntMaps;// key出现次数
        int cnt;

        public FreqStack() {
            cntValueMap = new HashMap();
            keyCntMaps = new HashMap<>();
            cnt = 0;
        }

        public void push(int val) {
            // 次数增加
            keyCntMaps.put(val, keyCntMaps.getOrDefault(val, 0) + 1);
            int curCnt = keyCntMaps.get(val);
            if (!cntValueMap.containsKey(curCnt)) { // 判断是否出现了该次数，1次、2次、3次...
                cntValueMap.put(curCnt, new ArrayList<>());
            }
            cntValueMap.get(curCnt).add(val);// 将 val 存到对应次数的集合里
            cnt = Math.max(curCnt, cnt); // 更新最大值
        }

        public int pop() {
            List<Integer> topTimesValues = cntValueMap.get(cnt); // 获取最大频率的集合
            Integer ans = topTimesValues.remove(topTimesValues.size() - 1); // 移除最后一个
            if (topTimesValues.size() == 0) { // 如果存放该次数的集合已经为空，则移除该次数的key
                cntValueMap.remove(cnt--);
            }
            int curCnt = keyCntMaps.get(ans);
            if (curCnt == 1) { // 如果该key是最后一个，则删除记录key的值
                keyCntMaps.remove(ans);
            } else { // 否则更新次数-1
                keyCntMaps.put(ans, curCnt - 1);
            }
            return ans;
        }
    }
}
